Complex Brain Networks: A Graph-Theoretical Analysis

229

9.3.3

Matching Index

The matching index of a pair of nodes {u, v} in a graph is determined by

calculating the ratio of the number of their common neighbors to the number

of the union of all of their neighbors. Matching indices for node pairs (a, b) and

(b, c) of the graph in Figure 9.2 are 0.5 and 0.2 respectively.This parameter

is used to determine how similar two nodes are, since two nodes with a high

matching index have many common neighbors, thus, their main function in

the network may be similar. For example, two proteins in a protein interface

network with many common neighbors may have similar tasks to perform.

9.3.4

Centrality

Centrality is yet another measure to determine the importance of nodes or

edges in a complex network. This parameter is evaluated by calculating short-

est paths over the nodes or edges. Various centrality parameters provide sig-

nificant importance of nodes or edges in a graph representing a complex brain

network.

9.3.4.1

Closeness Centrality

The closeness centrality C(v) of a node v in a graph provides information on

how central that node is in the graph. It is determined for a node v by finding

the sum of all distances from v to all other nodes and taking the reciprocal of

this sum as in Eqn. 9.5 where d(u, v) shows the distance between vertices u

and v

C(v) =

1



v∈V ^{d(u, v)}

(9.5)

The distances may be calculated using the breadth-first-search algorithm in

an unweighted graph where edges do not have weights associated with them.

Dijkstra’s shortest path algorithm or Bellman-Ford algorithm [3] may be used

to evaluate shortest paths between the nodes of a weighted graph with weights

associated with edges commonly display the costs of transferring data over

those edges. The closeness centrality values for the vertices in the graph of

Figure 9.2 are as follows: C(a) = 0.08, C(b) = 0.11, C(c) = 0.14, C(d) = 0.09,

C(e) = 0.10, C(f) = 0.11, and C(g) = 0.13. The node c has the highest value

since it is more central than other nodes as can be seen.

9.3.4.2

Vertex Betweenness Centrality

The importance of a node v in a graph may be evaluated by finding the

percentage of shortest paths that run through v called its vertex betweenness

centrality V C(v), since a high value of this parameter means node v is vital

in transferring data among all nodes. The V C(v) value of a vertex v may

be determined using Eqn. 9.6 where σst shows the number of shortest paths

between all nodes s and t other than node v, and σst(v) is the number of